package com.shm.leetcode;

import java.util.TreeSet;

/**
 * 220. 存在重复元素 III
 * 在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。
 *
 * 如果存在则返回 true，不存在返回 false。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,2,3,1], k = 3, t = 0
 * 输出: true
 * 示例 2:
 *
 * 输入: nums = [1,0,1,1], k = 1, t = 2
 * 输出: true
 * 示例 3:
 *
 * 输入: nums = [1,5,9,1,5,9], k = 2, t = 3
 * 输出: false
 *
 * @author SHM
 */
public class ContainsNearbyAlmostDuplicate {
    //超时
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = Math.max(i-k,0); j < i; j++) {
                if (Math.abs((long)nums[i]-(long)nums[j])<=(long)t){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 方法二 （二叉搜索树） 【通过】
     * 思路
     *
     * 如果窗口中维护的元素是有序的，只需要用二分搜索检查条件二是否是满足的就可以了。
     * 利用自平衡二叉搜索树，可以在对数时间内通过 插入 和 删除 来对滑动窗口内元素排序。
     * 算法
     *
     * 方法一真正的瓶颈在于检查第二个条件是否满足需要扫描滑动窗口中所有的元素。因此我们需要考虑的是有没有比全扫描更好的方法。
     *
     * 如果窗口内的元素是有序的，那么用两次二分搜索就可以找到 x+tx+t 和 x-tx−t 这两个边界值了。
     *
     * 然而不幸的是，窗口中的元素是无序的。这里有一个初学者非常容易犯的错误，那就是将滑动窗口维护成一个有序的数组。虽然在有序数组中 搜索 只需要花费对数时间，但是为了让数组保持有序，我们不得不做插入和删除的操作，而这些操作是非常不高效的。想象一下，如果你有一个kk大小的有序数组，当你插入一个新元素xx的时候。虽然可以在O(\log k)O(logk)时间内找到这个元素应该插入的位置，但最后还是需要O(k)O(k)的时间来将xx插入这个有序数组。因为必须得把当前元素应该插入的位置之后的所有元素往后移一位。当你要删除一个元素的时候也是同样的道理。在删除了下标为ii的元素之后，还需要把下标ii之后的所有元素往前移一位。因此，这种做法并不会比方法一更好。
     *
     * 为了能让算法的效率得到真正的提升，我们需要引入一个支持 插入，搜索，删除 操作的 动态 数据结构，那就是自平衡二叉搜索树。自平衡 这个词的意思是，这个树在随机进行插入,删除操作之后，它会自动保证树的高度最小。为什么一棵树需要自平衡呢？这是因为在二叉搜索树上的大部分操作需要花费的时间跟这颗树的高度直接相关。可以看一下下面这棵严重左偏的非平衡二叉搜索树。
     *
     *
     *             6
     *            /
     *           5
     *          /
     *         4
     *        /
     *       3
     *      /
     *     2
     *    /
     *   1
     * 图 1. 一个严重左偏的非平衡二叉搜索树。
     *
     * 在上面这棵二叉搜索树上查找一个元素需要花费 线性 时间复杂度，这跟在链表中搜索的速度是一样的。现在我们来比较一下下面这棵平衡二叉搜索树。
     *
     *
     *           4
     *         /   \
     *        2     6
     *       / \   /
     *      1   3  5
     * 图2. 一颗平衡的二叉搜索树
     *
     * 假设这棵树上节点总数为 nn，一个平衡树能把高度维持在 h = \log nh=logn。因此这棵树上支持在 O(h) = O(\log n)O(h)=O(logn) 时间内完成 插入，搜索，删除 操作。
     *
     * 下面给出整个算法的伪代码：
     *
     * 初始化一颗空的二叉搜索树 set
     * 对于每个元素xx，遍历整个数组
     * 在 set 上查找大于等于xx的最小的数，如果s - x \leq ts−x≤t则返回 true
     * 在 set 上查找小于等于xx的最大的数，如果x - g \leq tx−g≤t则返回 true
     * 在 set 中插入xx
     * 如果树的大小超过了kk, 则移除最早加入树的那个数。
     * 返回 false
     * 我们把大于等于 xx 的最小的数 ss 当做 xx 在 BST 中的后继节点。同样的，我们能把小于等于 xx 最大的数 gg 当做 xx 在 BST 中的前继节点。ss 和 gg 这两个数是距离 xx 最近的数。因此只需要检查它们和 xx 的距离就能知道条件二是否满足了。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n \log (\min(n,k)))O(nlog(min(n,k)))
     * 我们需要遍历这个 nn 长度的数组。对于每次遍历，在 BST 中 搜索，插入 或者 删除 都需要花费 O(\log \min(k, n))O(logmin(k,n)) 的时间。
     *
     * 空间复杂度：O(\min(n,k))O(min(n,k))
     * 空间复杂度由 BST 的大小决定，其大小的上限由 kk 和 nn 共同决定。
     *
     * 笔记
     *
     * 当数组中的元素非常大的时候，进行数学运算可能造成溢出。所以可以考虑使用支持大数的数据类型，例如 long。
     *
     * C++ 中的 std::set，std::set::upper_bound 和 std::set::lower_bound 分别等价于 Java 中的 TreeSet，TreeSet::ceiling 和 TreeSet::floor。Python 标准库不提供自平衡 BST。
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode/
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate_2(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Integer ceiling = set.ceiling(nums[i]);
            if (ceiling!=null&&ceiling<=(long)nums[i]+(long)t){
                return true;
            }
            Integer floor = set.floor(nums[i]);
            if (floor!=null&&nums[i]<=(long)floor+(long)t){
                return true;
            }
            set.add(nums[i]);
            if (set.size()>k){
                set.remove(nums[i-k]);
            }
        }
        return false;
    }


}
